By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 25, Issue 6, pp. 1123-1358

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

Martin Kummer

pp. 1123-1143

BibTeX  Abstract Full Text:  PDF

An $o(n^3 )$-Time Maximum-Flow Algorithm

Joseph Cheriyan, Torben Hagerup, and Kurt Mehlhorn

pp. 1144-1170

BibTeX  Abstract Full Text:  PDF

A Deterministic ${\operatorname{Poly}}(\log \log N)$-Time $N$-Processor Algorithm for Linear Programming in Fixed Dimension

Miklos Ajtai and Nimrod Megiddo

pp. 1171-1195

BibTeX  Abstract Full Text:  PDF

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines

Martin Dietzfelbinger, Miroslaw Kutylowski, and Rüdiger Reischuk

pp. 1196-1230

BibTeX  Abstract Full Text:  PDF

Lower Bounds for Geometrical and Physical Problems

Jürgen Sellen

pp. 1231-1253

BibTeX  Abstract Full Text:  PDF

Average and Randomized Complexity of Distributed Problems

Nechama Allenberg-Navony, Alon Itai, and Shlomo Moran

pp. 1254-1267

BibTeX  Abstract Full Text:  PDF

Learning Behaviors of Automata from Multiplicity and Equivalence Queries

Francesco Bergadano and Stefano Varricchio

pp. 1268-1280

BibTeX  Abstract Full Text:  PDF

Prefix Codes: Equiprobable Words, Unequal Letter Costs

Mordecai J. Golin and Neal Young

pp. 1281-1292

BibTeX  Abstract Full Text:  PDF

On Unapproximable Versions of $NP$-Complete Problems

David Zuckerman

pp. 1293-1304

BibTeX  Abstract Full Text:  PDF

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

Hans L. Bodlaender

pp. 1305-1317

BibTeX  Abstract Full Text:  PDF

An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String

Alberto Apostolico and Dany Breslauer

pp. 1318-1331

BibTeX  Abstract Full Text:  PDF

The Wakeup Problem

Michael J. Fischer, Shlomo Moran, Steven Rudich, and Gadi Taubenfeld

pp. 1332-1357

BibTeX  Abstract Full Text:  PDF

Erratum: Fast Parallel Computation of the Polynomial Remainder Sequence via Bezout and Hankel Matrices

Dario Bini and Luca Gemignani

p. 1358

BibTeX  Abstract Full Text:  PDF